package com.zyk.leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author zhangsan
 * @date 2021/4/13 13:48
 */
public class C1673 {

    // https://leetcode-cn.com/problems/find-the-most-competitive-subsequence/
    public static int[] mostCompetitive(int[] nums, int k) {
        // 单调栈
        Deque<Integer> ms = new ArrayDeque<>();
        ms.addLast( -1);     // 给定数组元素都大于0, 所以-1永远不可能出栈, 及后序操作我可以不用判空
        for (int r = 0; r < nums.length; r++) {
            while (nums[r] < ms.peekLast() && k - ms.size() + 1 < nums.length - r) {
                ms.pollLast();
            }
            if (ms.size() < k + 1) {
                ms.addLast(nums[r]);
            }
        }
        int[] ans = new int[k];
        while (k > 0) {
            ans[--k] = ms.pollLast();
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] nums = {3, 5, 2, 6};
        int k = 2;
        System.out.println(Arrays.toString(mostCompetitive(nums, k)));
    }


}
